package top.zhanglingxi.algorithms;

import cn.hutool.core.util.RandomUtil;
import top.zhanglingxi.enums.PointEnum;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Prim算法生成迷宫
 * @author ZWX
 */
public class PrimGenerateLabyrinth implements IGenerateLabyrinth {

    @Override
    public Point[][] generateLabyrinth(int length, int width) {
        // 参数校验
        if (length < 2 || length % 2 == 0) {
            throw new IllegalArgumentException("length必须大于1并且为奇数！");
        }

        if (width < 2 || width % 2 == 0) {
            throw new IllegalArgumentException("width必须大于1并且为奇数！");
        }

        // 长 路点个数
        int a = (length - 1) / 2;
        // 宽 路点个数
        int b = (width - 1) / 2;

        // 初始化迷宫
        Point[][] labyrinth = new Point[length][width];
        // 待选路点列表
        // 将整个地图初始化为墙
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < width; j++) {
                labyrinth[i][j] = new Point(i, j, PointEnum.GREY);
            }
        }
        // 随机选择一个路点，将它变成路，并将它四周的路点加入进待选路点（列表）
        int aRandom = RandomUtil.randomInt(a);
        int bRandom = RandomUtil.randomInt(b);
        // 路点x坐标
        int roadPointX = aRandom * 2 + 1;
        // 路点y坐标
        int roadPointY = bRandom * 2 + 1;
//        Point point = labyrinth[roadPointX][roadPointY];
        Point point = labyrinth[1][1];
        point.setType(PointEnum.WHITE);
        List<Point> toBeSelectedRoadPoints = new ArrayList<>(getAroundRoadPointList(labyrinth, point));

        // 当待选路点（列表）不为空时
        while (!toBeSelectedRoadPoints.isEmpty()) {
            // 从待选路点中随机选一个路点A，变成路点并移出待选路点（列表）
            Point roadPointA = toBeSelectedRoadPoints.remove(RandomUtil.randomInt(toBeSelectedRoadPoints.size()));
            roadPointA.setType(PointEnum.WHITE);
            List<Point> aroundRoadPointList = getAroundRoadPointList(labyrinth, roadPointA);

            // 将A与它四周的随机一个已经变成路的路点B打通(将A变成路，将A和B中间的墙点变成路)
            List<Point> roadPointList = aroundRoadPointList.stream()
                    .filter(item -> item.getType() == PointEnum.WHITE)
                    .collect(Collectors.toList());
            Point roadPointB = roadPointList.get(RandomUtil.randomInt(roadPointList.size()));
            // 判断路点B的位置
            // 路点B在路点A的右侧
            if (roadPointB.getX() - roadPointA.getX() == 2) {
                labyrinth[roadPointB.getX() - 1][roadPointB.getY()].setType(PointEnum.WHITE);
            }
            // 路点B在路点A的左侧
            if (roadPointB.getX() - roadPointA.getX() == -2) {
                labyrinth[roadPointB.getX() + 1][roadPointB.getY()].setType(PointEnum.WHITE);
            }
            // 路点B在路点A的下面
            if (roadPointB.getY() - roadPointA.getY() == 2) {
                labyrinth[roadPointB.getX()][roadPointB.getY() - 1].setType(PointEnum.WHITE);
            }
            // 路点B在路点A的上面
            if (roadPointB.getY() - roadPointA.getY() == -2) {
                labyrinth[roadPointB.getX()][roadPointB.getY() + 1].setType(PointEnum.WHITE);
            }

            // 将A四周不是路的路点加入到待选路点
            List<Point> wellPointList = aroundRoadPointList.stream()
                    .filter(item -> item.getType() != PointEnum.WHITE)
                    .collect(Collectors.toList());
            for (Point wellPoint : wellPointList) {
                if (!toBeSelectedRoadPoints.contains(wellPoint)) {
                    toBeSelectedRoadPoints.add(wellPoint);
                }
            }

//            toBeSelectedRoadPoints.addAll(wellPointList);
        }
        return labyrinth;
    }

    /**
     * 获取路点周围的所有路点
     * @param labyrinth 迷宫
     * @param point 路点
     * @return 该路点周围的所有路点
     */
    private List<Point> getAroundRoadPointList(Point[][] labyrinth, Point point) {
        int length = labyrinth.length;
        int width = labyrinth[0].length;
        int roadPointX = point.getX();
        int roadPointY = point.getY();
        ArrayList<Point> aroundRoadPointList = new ArrayList<>();
        // 左 路点
        if (roadPointX - 2 > 0) {
            aroundRoadPointList.add(labyrinth[roadPointX - 2][roadPointY]);
        }
        // 右 路点
        if (roadPointX + 2 < length) {
            aroundRoadPointList.add(labyrinth[roadPointX + 2][roadPointY]);
        }
        // 上 路点
        if (roadPointY - 2 > 0) {
            aroundRoadPointList.add(labyrinth[roadPointX][roadPointY - 2]);
        }
        // 下 路点
        if (roadPointY + 2 < width) {
            aroundRoadPointList.add(labyrinth[roadPointX][roadPointY + 2]);
        }

        return aroundRoadPointList;
    }

}
